package arrAndstr;

import java.util.*;

public class T173 {


    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class BSTIterator {
        private Queue<Integer> queue = new ArrayDeque<>();

        public BSTIterator(TreeNode root) {
            LDR(root, queue);
        }

        private void LDR(TreeNode root, Queue<Integer> queue) {
            if (root == null)   return;

            LDR(root.left, queue);
            queue.add(root.val);
            LDR(root.right, queue);
        }

        public int next() {
            return queue.poll();
        }

        public boolean hasNext() {
            return queue.size() != 0;
        }
    }
}
